package com.logbug.sort;

import java.util.Arrays;

// 合并两个有序数组
public class MergeSortedArray {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 3, 6, 9};
        int[] arr2 = new int[]{2, 3, 7, 8, 9};
        int[] merge = merge(arr1, arr2);
        System.out.println(Arrays.toString(merge));
    }

    public static int[] merge(int[] arr1, int[] arr2) {
        int[] arr = new int[arr1.length + arr2.length];
        int i = 0, j = 0, t = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                arr[t++] = arr1[i++];
            } else {
                arr[t++] = arr2[j++];
            }
        }
        while (i < arr1.length) {
            arr[t++] = arr1[i++];
        }
        while (j < arr2.length) {
            arr[t++] = arr2[j++];
        }
        return arr;

    }

    public static int[] merge2(int[] arr1, int[] arr2) {
        int[] arr = new int[arr1.length + arr2.length];
        int i = 0, j = 0, t = 0;
        while (i + j < arr1.length + arr2.length) {
            if (i == arr1.length ) {
                // 第一个数组的元素全部被取出了，直接将第二个数组的剩余元素放入目标数组
                arr[t++] = arr2[j++];
            } else if (j == arr2.length ) {
                // 第二个数组的元素全部被取出了，直接将第一个数组的剩余元素放入目标数组
                arr[t++] = arr1[i++];
            } else if (arr1[i] < arr2[j]) {
                // 两个数组都有元素，正常进行
                arr[t++] = arr1[i++];
            } else {
                arr[t++] = arr2[j++];
            }
        }

        return arr;

    }
}
